package com.aikon.wht.paoshan.alg;

/**
 * 约瑟夫问题，循环链表解法。
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfJosephas {

    // 共10人，依次报数，第5个人自杀，他之后的第一个人开始报数，第五个人自杀，依次类推
    // 1 2 3 4 5 6 7 8 9 10
    // 1 2 3 4 x 6 7 8 9 10              5
    // 1 2 3 4 x 6 7 8 9 x               10
    // 1 2 3 4 x x 7 8 9 x               6
    // 1 x 3 4 x x 7 8 9 x               2
    // 1 x 3 4 x x 7 8 x x               9
    // 1 x 3 4 x x 7 x x x               8
    // x x 3 4 x x 7 x x x               1
    // x x 3 x x x 7 x x x               4
    // x x 3 x x x x x x x               7

    public static void main(String[] args) {
        System.out.println("survivor " + findSurvivor(100000000, 3));
    }

    /**
     * 创建长度为n的循环链表
     *
     * @param n
     * @return
     */
    public static Jews createJewsLink(int n) {
        if (n == 1) {
            Jews head = new Jews(1);
            head.setNext(head);
            return head;
        }
        Jews head = new Jews(1);
        Jews next = head;
        for (int i = 2; i <= n; i++) {
            Jews j = new Jews();
            j.setId(i);
            next.setNext(j);
            next = j;
        }
        // 尾指向头
        next.setNext(head);
        return head;
    }

    public static int findSurvivor(int n, int m) {
        // 创建犹太人循环链表
        Jews jewsLink = createJewsLink(n);
        Jews currentJews = jewsLink;
        currentJews = lookIntoLinkWhile(m, currentJews);
        return currentJews.getId();
    }

    /**
     * 报数找到第m个人，kill并从m+1报数直到找到幸存者，递归调用有stackoverflow风险
     *
     * @param m
     * @param currentJews
     * @return
     */
    private static Jews lookIntoLink(int m, Jews currentJews) {
        // 找到幸存者，返回
        if (currentJews.getNext().equals(currentJews)) {
            return currentJews;
        }
        // 从1开始报数，找到自杀者前一个人
        for (int i = 1; i < m - 1; i++) {
            currentJews = currentJews.getNext();
        }
        // 自杀（自杀者前一个指向自杀者后一个）
//        System.out.println("kill " + currentJews.getNext().getId());
        currentJews.setNext(currentJews.getNext().getNext());
        // 从自杀者后一个重新开始，直到找到幸存者
        return lookIntoLink(m, currentJews.getNext());
    }

    /**
     * 报数找到第m个人，kill并从m+1报数直到找到幸存者
     *
     * @param m
     * @param currentJews
     * @return
     */
    private static Jews lookIntoLinkWhile(int m, Jews currentJews) {
        int cnt = 1;
        Jews pre = null;
        while (!currentJews.getNext().equals(currentJews)) {
            if (cnt == m) {
                cnt = 1;
                pre.setNext(currentJews.getNext());
                currentJews = currentJews.getNext();
            } else {
                cnt++;
                pre = currentJews;
                currentJews = pre.getNext();

            }
        }
        return currentJews;
    }


    public static class Jews {
        private int id;

        private Jews next;

        public Jews(int id) {
            this.id = id;
        }

        public Jews() {
        }

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        public Jews getNext() {
            return next;
        }

        public void setNext(Jews next) {
            this.next = next;
        }
    }


}